package com.atguigu.dac;

/**
 * @author RuiKnag
 * @create 2021-05-26-17:40
 */
/*
 * 分治算法是一种很重要的算法，字面上的解释”分而治之“。就是把一个复杂的问题分成两个或跟多个相同的或者相似的子问题，再把子问题分成
 * 更小的子问题。。。直到最后的子问题可以简单的直接求解，原问题的解就是子问题的合并。这个技巧是很多高效算法的基础。
 * 步骤：
 *   分解：将原问题分解为若干规模较小的问题，相对独立，与原问题形式相同的子问题
 *   解决：若子问题规模较小而容易被解决则直接解决，否则递归地解决各个子问题
 *   合并：将各个子问题的解合并为原来问题的解
 * 如排序算法（快速和归并）
 * 可以求解的经典问题
 * 二分搜索
 * 大整数乘法
 * 棋盘覆盖
 * 合并排序
 * 快速排序
 * 线性时间选择
 * 最接近近点对问题
 * 循环赛日问题
 * 汉诺塔
 * */


/*
* 如果只有一个盘：a->c
* 如果我们有n>=2，我们总是可以看作两个盘，一个最下面的盘，一个是最上面的盘
*   我们的移动顺序是先把最上面的移动到a->b,再把最下面的盘a->c,然后把最上面的盘b->c即可
*
*
* */
public class Hanoitower {
    public static void main(String[] args) {
        hanoiTower(80,'A','B','C');
    }

    public static void hanoiTower(int num,char a,char b,char c){
      if(num==1){
          System.out.println("第1个盘子从"+a+"-->"+c);
      }else{
          hanoiTower(num-1,a,c,b);
          System.out.println("第"+num+"个盘子从"+a+"-->"+c);
          hanoiTower(num-1,b,a,c);
      }
    }
}
